package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/sort-list/
 *  排序链表   归并排序
 * author: hongchen.liao
 * date:  2022/10/12
 */
public class _148_ {


     //Definition for singly-linked list.
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            //快慢指针找到中点
            ListNode fast, slow;
            fast = head.next;
            slow = head;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            //分割成两段
            ListNode tmp = slow.next;
            slow.next = null;
            //递归这个过程 不断分割排序
            ListNode left = sortList(head);
            ListNode right = sortList(tmp);
            //搞一个虚节点 合并结果
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;

            while(left != null && right != null){
                if(left.val < right.val){
                    p.next = left;
                    left = left.next;
                }else{
                    p.next = right;
                    right = right.next;
                }
                p = p.next;
            }
            p.next = left != null ? left : right;
            return dummy.next;
        }
    }

}
